﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingAlgorithms.Insertion
{
    /// <summary>
    /// 直接插入排序-插入排序
    /// </summary>
    /// <remarks>
    /// 分类 -------------- 内部比较排序
    /// 数据结构 ---------- 数组
    /// 最差时间复杂度 ---- O(n^2)
    /// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
    /// 平均时间复杂度 ---- O(n^2)
    /// 所需辅助空间 ------ O(1)
    /// 稳定性 ------------ 稳定
    /// </remarks>
    public class InsertionSort
    {
        //定义一个静态变量来保存类的实例
        private static InsertionSort _uniqueInstance=null;

        //定义一个标识确保线程同步
        private static readonly object locker = new object();

        /// <summary>
        /// 私有化构造函数，使外界不能创建该类实例
        /// </summary>
        private InsertionSort()
        { 
        }

        public static InsertionSort Instance
        {
            get
            {
                if (_uniqueInstance == null)
                {
                    lock (locker)
                    {
                        if (_uniqueInstance == null)
                        {
                            _uniqueInstance = new InsertionSort();

                        }
                    }
                }
                return _uniqueInstance;
            }
        }


        public void SortDesc(int[] a,int n)
        {
            int j = 0, temp = 0;
            for (int i = 1; i < n; i++)
            {
                temp = a[i];
                for (j = i - 1; j >= 0; j--)
                {
                    if (temp < a[j]) //如果插入的值小于某个值，则退出循环
                        break;
                    a[j + 1] = a[j];
                }
                a[j + 1] = temp;
                   
            }
        }

        public void SortAsc(int[] a, int n)
        {
            for (int i = 1; i < n; i++)
            {
                if (a[i] < a[i - 1]) //若第I个元素大于i-1个元素，直接插入，小于的话，移动有序表后插入
                {
                    int j = i - 1;
                    int x = a[i];    //复制为存储待排序元素
                    a[i] = a[i - 1]; //先后移一个元素
                    while (j >= 0 && x < a[j]) //查找在有序表的插入位置
                    {
                        a[j + 1] = a[j];
                        j--;              //元素前移
                    }
                    a[j + 1] = x;         //插入到正确的位置
                }
            }
        }

    }
}
